Sparse Table AQI Range Minimum Query Visualizer

📋 Problem Statement

The environmental department of a major city has collected daily Air Quality Index (AQI) data for the past N days. The AQI score of each day is stored in a centralized database, where lower AQI values mean better air quality. To support research and policy planning, the department must regularly answer queries such as: What was the best air quality recorded between Day L and Day R?

Since the AQI data is historical and fixed, and officials submit thousands of such range queries, your task is to design a system that can preprocess the data once using a Sparse Table and answer each Range Minimum Query efficiently.

📥 Input Format

First line: N (number of days, 1 ≤ N ≤ 20)
Second line: N space-separated integers (AQI values, 1 ≤ AQI[i] ≤ 100)
Third line: Q (number of queries, 1 ≤ Q ≤ 20)
Next Q lines: Two integers L and R (0 ≤ L ≤ R < N)

📤 Output Format

For each query, output a single integer representing the minimum AQI value in the range [L, R].

🎯 Sample Test Case 1

Input:

6
4 2 7 1 3 6
4
0 2
1 4
2 5
3 3

Output:

Explanation:

Query [0, 2]: min(4, 2, 7) = 2
Query [1, 4]: min(2, 7, 1, 3) = 1
Query [2, 5]: min(7, 1, 3, 6) = 1
Query [3, 3]: min(1) = 1

🎯 Sample Test Case 2

Input:

8
5 3 8 6 2 9 1 7
5
0 7
2 5
4 6
1 1
6 7

Output:

🧠 Sparse Table Algorithm

A Sparse Table is a data structure that allows answering range queries on static arrays in O(1) time after O(n log n) preprocessing. It's ideal for Range Minimum Query (RMQ) problems where the data doesn't change.

📊 Key Concept

The Sparse Table uses dynamic programming to precompute answers for all ranges whose lengths are powers of 2. For any query [L, R], we can compute the answer by taking the minimum of two overlapping power-of-2 ranges.

sparse[i][j] = minimum value in range starting at index i with length 2^j

🔧 Building the Sparse Table

// Initialize for length 1 (2^0)
for (int i = 0; i < n; i++) {
    sparse[i][0] = arr[i];
}

// Build for increasing powers of 2
for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 0; i + (1 << j) <= n; i++) {
        sparse[i][j] = min(sparse[i][j-1],
                          sparse[i + (1 << (j-1))][j-1]);
    }
}

🔍 Querying the Sparse Table

// Query minimum in range [L, R]
int query(int L, int R) {
    int length = R - L + 1;
    int k = log2(length);  // Largest power of 2 that fits

    return min(sparse[L][k],
              sparse[R - (1 << k) + 1][k]);
}

Key Insight: Any range can be covered by two overlapping power-of-2 ranges. For overlapping ranges in RMQ, taking the minimum of both gives the correct answer.

⚡ Complexity Analysis

Build: O(n log n) Query: O(1) Space: O(n log n)

Build: O(n log n) - fill table with all power-of-2 ranges
Query: O(1) - constant time lookup with two table accesses
Space: O(n log n) - store n × log(n) values

🆚 Comparison with Other Methods

Method	Build Time	Query Time	Update Support
Sparse Table	O(n log n)	O(1)	❌ Static
Segment Tree	O(n)	O(log n)	✅ Dynamic
Naive Approach	O(1)	O(n)	✅ Dynamic

📊 Input Configuration

Number of Days (N):

AQI Values (space-separated):

Queries (one per line, format: L R):

Normal

Highlighted

Result

📊 Current AQI Array State

🗂️ Sparse Table Structure

⚙️ Current Operation

Ready to build table...

Operation log will appear here...

🌍 Sparse Table AQI Visualizer